package EjercicioArbolBinario;

import java.util.Iterator;

import TDAArbolBinario.ArbolBinario;
import TDAArbolBinario.BinaryTree;
import TDAArbolBinario.EmptyTreeException;
import TDAArbolBinario.InvalidOperationException;
import TDALista.InvalidPositionException;
import TDALista.Position;
/**
 * Clase que encapsula dos métodos para resolver el siguiente ejercicio:</br>
 * Desarrolle un método que, recibiendo la <b>altura A</b> y un <b>iterador</b> de elementos correspondiente a un <a>árbol binario lleno T</a>, retorne un <a>nuevo árbol binario</a> cuyos elementos deben ser la <i>clonación de T</i>.</br> 
 * Tenga en cuenta que el iterador de elementos recibido realiza un recorrido en <b>preorden en T</b>. </br>
 * 
 * <b>Requiere:</b> <i>TDALista</i> y <i>TDAArbolBinario</i>.
 * @author FJoaquin (federico.joaquin@cs.uns.edu.ar)
 *
 */
public class EjercicioArbolBinario {
	/**
	 * Crea un árbol binario completo dada una altura y un iterador de elementos.
	 * Para esto, clona la estructura y elementos de otro árbol binario completo que es recorrido mediante el iterador, siguiendo un recorrido en preorden. 
	 * @param it Iterador del árbol binario completo a clonar, siguiendo un recorrido en pre-orden.
	 * @param altura Altura correspondiente al árbol binario completo a clonar.
	 * @retur Nuevo árbol binario completo.
	 */
	public static <E> BinaryTree<E> crear_arbol_completo(Iterator<E> it, int altura) {
		BinaryTree<E> toReturn = new ArbolBinario<E>();
		try {
			if (it.hasNext()) {
				E rotulo = it.next();
				toReturn.createRoot(rotulo);
				if (altura>0)
					clonar_arbol_completo(toReturn, toReturn.root(), it, altura-1);
			}
		}catch(InvalidOperationException | EmptyTreeException e) {
			toReturn = null;
		}
		return toReturn;
	}
	/**
	 * Clona el subárbol binario completo a partir de la posición padre de árbol.
	 * Para esto considera la altura de las raíces de los subárboles a clonar, y el recorrido en preorden que sigue el iterador de elementos del árbol binario clonado.
	 * @param padre Posición a la que se agregarán el subárbol izquierdo y derecho.
	 * @param it Iterador del subárbol binario completo a clonar, siguiendo un recorrido en pre-orden.
	 * @param altura Altura correspondiente del nodo padre en el árbol binario clonado.
	 */
	protected static <E> void clonar_arbol_completo(BinaryTree<E> arbol, Position<E> padre, Iterator<E> it, int altura) {
		Position<E> nuevoPadre;
		E rotulo; 
		try {
			//Clonación de las hojas de árbol.
			if (altura == 0) {
				rotulo = it.next();
				arbol.addLeft(padre, rotulo);
				rotulo = it.next();
				arbol.addRight(padre, rotulo);
			}else {
				//Clonación de nodos internos del árbol.
				rotulo = it.next();
				nuevoPadre = arbol.addLeft(padre, rotulo);
				clonar_arbol_completo(arbol, nuevoPadre, it, altura-1);
				rotulo = it.next();
				nuevoPadre = arbol.addRight(padre, rotulo);
				clonar_arbol_completo(arbol, nuevoPadre, it, altura-1);
			}
		}catch(InvalidOperationException | InvalidPositionException e){}
	}
}
